2016本科插班生考试大纲
（考试科目：数据结构）
Ⅰ考试性质
普通高等学校本科插班生（又称专插本）招生考试是由专科毕业生参加的选拔性考试。高等学校根据考生的成绩，按照已确定的招生计划，德、智、体全面衡量，择优录取。因此，本科插班生考试应有较高信度、效度、必要的区分度和适当的难度。
Ⅱ考试内容
总体要求：理解数据结构的基本概念；把握数据的逻辑结构、存储结构及其差异，以及各种基本操作的实现。把握基本的数据处理原理和方法的基础上，能够对算法进行设计与分析。能够选择合适的数据结构和方法进行问题求解。
绪论
⒈ 考试内容
⑴ 数据结构等相关基本概念。
⑵ 算法的定义、特征与设计要求。
⑶ 时空复杂度分析。
⒉ 考试要求
⑴ 了解数据结构等相关基本概念。
⑵ 了解算法的定义、特征与设计要求。
⑶ 掌握算法的时空复杂度分析方法。
第一章 线性表
⒈ 考试内容
⑴ 线性表的定义和基本操作。
⑵ 线性表的实现：顺序存储结构和链式存储结构；
⑶ 线性表的应用。
⒉ 考试要求
⑴ 掌握线性表的定义和基本操作。
⑵ 掌握线性表的顺序存储与链式存储实现。
第二章 栈和队列
⒈考试内容
⑴ 栈的基本概念。
⑵ 栈的表示和实现。
⑶ 栈的应用。
⑷ 队列的基本概念。
⑸ 队列的表示和实现。
⑹ 循环队列和链式队列。
⒉考试要求
⑴ 掌握栈的基本概念、表示、实现和应用。
⑵ 掌握队列的基本概念、表示和实现。
⑶ 掌握循环队列的实现。
第三章 串、数组和广义表
⒈ 考试内容
⑴ 串的定义、表示和实现。
⑵ 串的基本操作。
⑶ 数组的定义、表示和实现。
⑷ 矩阵的概念、特殊矩阵和稀疏矩阵。
⑸ 广义表的定义、存储结构。
⒉ 考试要求
⑴ 掌握串的定义、表示和基本操作的实现，特别是模式匹配算法。
⑵ 掌握数组的定义、表示和实现及与矩阵的关系，掌握特殊矩阵和稀疏矩阵压缩方法。
⑵ 了解广义表的定义、存储结构。
第四章 树与二叉树
⒈ 考试内容
⑴ 树的基本概念及存储结构。
⑵ 二叉树的基本概念、二叉树的存储结构、二叉树的遍历。
⑶ 森林的概念、存储结构。
⑷ 树、森林与二叉树的转换。
⑸ 树和森林的遍历。
⑹ 哈夫曼树的概念和应用。
⒉考试要求
⑴ 了解树的基本概念及存储结构、森林的概念及存储结构。
⑵ 掌握二叉树的基本概念、二叉树的存储结构、二叉树的遍历。
⑶ 掌握树、森林与二叉树的转换方法。
⑷ 了解树和森林的遍历。
⑸ 掌握哈夫曼树的概念、求解方法和应用。
第五章 图
⒈考试内容
⑴ 图的定义和概念、图的存储结构。
⑵ 图的遍历。
⑶ 图的应用：最小生成树、拓扑排序、关键路径、最短路径问题。
⒉考试要求
⑴ 了解图的相关定义。
⑵ 掌握图的存储结构、图的遍历方法。
⑶ 掌握图的最小生成树、拓扑排序、关键路径、最短路径的应用。
第六章 查找
⒈考试内容
⑴ 静态查找表、动态查找表与哈希表的基本概念。
⑵ 顺序表、有序表、静态树表、索引顺序表的查找。
⑶ 二叉排序树和平衡二叉树的基本概念与实现。
⑷ B_树和B+树的基本概念。
⑸ 哈希函数的构造方法、冲突处理的方法。
⑹ 哈希表的查找和分析。
⒉考试要求
⑴ 了解静态查找表、动态查找表与哈希表的基本概念，了解B_树和B+树的基本概念。
⑵ 掌握顺序表、有序表、静态树表、索引顺序表的查找。
⑶ 掌握二叉排序树和平衡二叉树的基本概念与实现。
⑷ 掌握哈希函数的构造方法、冲突处理的方法，查找和分析方法。
第七章 排序
⒈考试内容
⑴ 排序的相关概念
⑵ 插入排序、交换排序、选择排序、归并排序、基数排序的概念和实现方法
⑶ 排序方法的比较
⒉考试要求
⑴ 了解排序的相关概念。
⑵ 掌握插入排序、交换排序、选择排序、归并排序、基数排序的概念和实现方法。
⑶ 了解不同排序算法的特点与适用范围。
Ⅲ.考试形式及试卷结构
一、考试形式
闭卷、笔试。试卷满分为100分，考试时间为120分钟。
二、试卷题型比例
填空题：约占20%；
单选题：约占30%；
应用题：约占30%；
程序题填空题：约占10%。
算法设计题：约占10%。
二、试卷题型示例及答案
1．填空题：
例：深度为4的完全二叉树，至少有( )个结点。
2．单选题：
例：如果一个栈的入栈序列是1、2、3、4、5，则栈不可能得到的出栈序列为（ ）。
A. 54321 B. 45321 C. 43512 D. 12345
3．应用题：
例：试列出下图中全部可能的拓扑有序序列。
4．算法填空题：
例：下面的函数List_insert( )实现在单链表L的第i个元素之前插入一个值为e的结点。
typedef struct Lnode
{ Elemtype data;
struct Lnode *next;
} LNode,*LinkList;
void List_insert(LinkList &L, int i, Elemtype e)
{ LinkList p=L, s ;
int j=0;
while ( p!=NULL && j< i-1 )
{ p=p->next; j++; }
s=( LinkList*)malloc Lnode(sizeof(LinkList));
s->data=___________;
s->next=p->next;
______________________;
}
5．算法设计题：
例：设二叉树的结点结构如下，用C语言完成函数count，统计二叉树T中非叶子结点的个数。
struct BiTree
{ int data;
struct BiTree *lchild, *rchild ;
};
int count(struct BiTree *T)
{
}
Ⅳ. 参考书目
① 《数据结构》（C语言版）严蔚敏主编，清华大学出版社，2012.5。
